Technology Client Server 2008'2
	Home Search Editions Contacts k-press.ru

Subscription to our publications continues! Did you remember to subscribe?

Device and cryptanalysis of a UUID generator in Windows

Author: Nikolay Denishchenko

Published: 07/29/2008

“I usually have plot songs, 
but this song has no plot. 
It would seem a set of words. 
No - this is a disturbing song. ”

V. Vysotsky about the song "Sail"

Realizing myself a full account of the fact that the word “cryptanalysis”, so unceremoniously used in the title of the article, can entail a real storm of righteous criticism, I still do not hurry to part with it and do not even intend to deprive the prefix “crypto”. Of course, in itself, the WinAPI function UuidCreate, which has become the subject of this study, has nothing to do with cryptography. Her modest part is to create unique identifiers (Universally Unique Identifiers) that comply with RFC4122 requirements. However, for some reason, those who want to prick nuts with a microscope do not stop. On the contrary, I increasingly come across attempts to employ UuidCreate as a pseudo-random number generator (PRNG).

The reasons for this phenomenon, in my opinion, several. First, the values ​​of identifiers seem random and independent (we are baptized three times). Secondly, the algorithm of the UUID-generator has not yet been published and, as far as I know, there is not a single trustworthy work where its properties would be described. Thirdly, the official and plenipotentiary Windows PRNG - the CryptGenRandom function - loses UuidCreate in simplicity and accessibility (it’s enough to remember that using CryptGenRandom implies a date with CryptoAPI, and not every programmer will end this date with a tumultuous novel).

So, for example, having met once with a colleague from a telecommunications company over a glass of good Czech beer, I learned a rather curious fact. It turns out that PIN codes for express payment cards of this “far-sighted” commercial organization are generated on MS SQL Server using the newid function (whose mask hides all the same UuidCreate), and no additional transformations are performed on the values ​​obtained. Having decided at first that the "author" burned, I expressed emotions in the best traditions of the Przhevalsky horse, but a second later I regretted it. The bewilderment on the face of the interlocutor definitely indicated the sincerity of his words and, if I had a pocket Bible at hand, I am sure that he would swear on it. There was no Bible, so I had to swear in the latest issue of the magazine "MAXIM".

Then, unfortunately, I did not manage to find weighty arguments in favor of the inadmissibility of using UuidCreate for such purposes, and until the last drop of beer, each of us remained in our opinion. However, the revelations colleagues for a long time did not give me rest. To finally dot the i, I decided to check how feasible the following two scenarios.

Scenario 1

The international operator of cellular and cellular communications, Give Kilo Sala, known after the re-branding under the brand name “Hello, Laundry?”, Is preparing to introduce to its subscribers a new tariff plan “Gluhonema”. In addition to the unprecedentedly low cost of one minute of conversation with the indigenous population of Franz Josef Land, the tariff gives you the opportunity to download the ringtone “No sound in the garden”.

The company is optimistic about the future and expects to increase its presence in the market of long-distance services. Anticipating a large increase in the number of subscribers, the leadership instructs the secret department "White Collars", which includes employees only with an impeccable reputation, to release a new series of express payment cards.

A special physical server is assigned to this good deed, which is prepared by system administrator Vasily Razdolbaev (Nordic character, not married).

Next, we describe the events in chronological order.

Morning, April 14, Monday. Vasily installs on the machine OS Windows and MS SQL Server 2008.

Evening is April 14, Monday. A commission from among the employees of the secret department checks the server for spyware and makes a conclusion: no malicious code was detected on the machine. The server, without shutting down, is moved to an underground bunker completely cut off from the outside world (lead walls 2 meters thick, interception of information is completely excluded, only “White collars” have access to the room).

Evening, April 15, Tuesday. Vasily goes to the most ruthless corporate event in his life, set up on the occasion of the release of the new tariff. In karaoke performs bawdy songs, dances naked on the table and clings to Masha Bucket from the accounting department. In other words, behaves like a real gentleman.

And at this time ... While the system administrator is relaxing, White Collars generate PIN codes for a new series of express payment cards. The T-SQL function NEWID is used as the source of random numbers (which, as will be shown below, is equivalent to calling UuidCreate). PIN codes received in this way are immediately applied to payment cards. When the procedure is fully completed, the server under the vigilant control of the guards armed to the teeth is taken to the nearest metallurgical plant, where it is burned in a blast furnace.

Morning, April 16, Wednesday. New express payment cards go on sale. Vasily Razdolbaev finds himself in a garbage can outside the Moscow Ring Road.

Attention, the question is: can Vasily, without resorting to rectal cryptanalysis of secret service employees, recover the PIN codes of the entire series of cards, and what does he need to do to do this?

Scenario 2

Suppose the server is not destroyed. Moreover, the system administrator was able to access it only on Wednesday, when the cards were already on sale. Does Vasily still have a chance to get PINs, given that they were deleted from the database by “White Collars”?

To more or less clearly answer these intriguing questions, we have to look under the hood of UuidCreate.

Tip of iceberg

Unfortunately, the official documentation we have at our disposal (an article in MSDN [4] and the text RFC4122 [1]) can only shed light on the structure of the return value, so there is no more benefit from it than from the previously mentioned journal MAXIM.

Function Definition (rpcdce.h):

RPCRTAPI RPC_STATUS RPC_ENTRY UuidCreate (Out UUID RPC_FAR * Uuid);

The structure of the return parameter Uuid (guiddef.h):

typedef  struct _GUID
{
  unsigned  long   Data1;
  unsigned  short Data2;
  unsigned  short Data3;
  unsigned  char   Data4 [8];
} GUID;

typedef GUID UUID;

UUID identifiers are often written as a text string:

{G ₁ G ₂ G ₃ G ₄ -G ₅ G ₆ -G ₇ G ₈ -G ₉ G ₁₀ -G ₁₁ G ₁₂ G ₁₃ G ₁₄ G ₁₅ G ₁₆ }

where G _x is the value of the corresponding byte of the structure in hexadecimal representation:

Data1 = G ₄ G ₃ G ₂ G ₁

Data2 = G ₆ G ₅

Data3 = G ₈ G ₇

Data4 = G ₉ G ₁₀ G ₁₁ G ₁₂ G ₁₃ G ₁₄ G ₁₅ G ₁₆

According to [1], the first two bits of the G ₉ define the format in which it is necessary to interpret the value of the identifier. In the case of UuidCreate, they are always equal to 10, therefore, the format must fully meet the requirements of RFC4122, which gives us the right to treat the four high bits of G ₇ as the version number of the algorithm. Our experimental set sequence 0100 in them (version 4, “The randomly or pseudo-randomly generated version”), so the remaining 122 bits of the structure must be filled in randomly. Is it really - now find out.

Autopsy revealed

We will prepare rpcrt4.dll (see Appendix B for a list of the versions examined) using the inhuman capabilities of the IDA Pro disassembler and the Visual Studio 2005 debugger, since it is in this library that the UUID generator is hidden from prying eyes.

We begin, of course, with the UuidCreate function.

RPCRTAPI RPC_STATUS RPC_ENTRY UuidCreate (
    OUT UUID __RPC_FAR * Uuid
)
{
  RPC_STATUS ret;

  ret = GenerateRandomNumber; ((BYTE *) Uuid, sizeof (UUID));

  if (ret == RPC_S_OK) {

    // Install the version 
    Uuid-> Data3 = (Uuid-> Data3 & 0x0fff) | 0x4000;

    // swear allegiance to RFC4122 format
    Uuid-> Data4 [0] = (Uuid-> Data4 [0] & 0x3F) | 0x80;
  };

  return ret;
};

In addition to calling GenerateRandomNumber, the function body contains nothing new for us. We cut further.

// RC4 instance state 
typedef  struct _RC4_INSTANCE_STATE {
  BYTE SBOX [256];   // S-block 
  BYTE i;           // Register RC4 
  BYTE j;     // Register RC4
} RC4_INSTANCE_STATE, * PRC4_INSTANCE_STATE;

// RC4 instance 
typedef  struct _RC4_INSTANCE
{
  // Number of bytes of the instance
  DWORD Accumulator;   
  // Critical section for thread synchronization
  CRITICAL_SECTION CS;  
  // RC4 instance status
  RC4_INSTANCE_STATE State;   
}
RC4_INSTANCE, * pRC4_INSTANCE;

// Generator state 
typedef  struct _RC4_CONTEXT
{
  DWORD InstanceCount;       // Total number of RC4 instances 
  DWORD AlwaysOne;           // Reserved. Always equal to 1 
  pRC4_INSTANCE Rc4Ins [8];   // RC4 instances
} RC4_CONTEXT, * pRC4_CONTEXT;     

// Global variable that determines the state of the UUID generator
RC4_CONTEXT g_rc4SafeCtx;
// Global variable defining the selection of the RC4 instance 
DWORD g_rc4TotalRequests = 0;

RPC_STATUS GenerateRandomNumber (BYTE * pbData, DWORD cbData) 
{

  // Total number of bytes of output of the current RC4 instance 
  // since its initialization

  DWORD Accumulator = 0;  

  // Number of the current RC4 instance
  DWORD InstNum;

  // Buffer for RC4 key, if initialization is required
  PVOID RandomKey;

  rc4_safe_select (& g_rc4SafeCtx, & InstNum, & Accumulator);

  if (Accumulator> = 500000)
  {
    //Initialization
    
    // Generate a pseudo-random key for RC4 
    if (! SystemFunction036 (RandomKey, 256))
       return RPC_S_OUT_OF_MEMORY;

    // Initialize the RC4 instance
    rc4_safe_key (& g_rc4SafeCtx, InstNum, 256, (BYTE *) RandomKey);
  };

  // Generate UUID value using RC4 algorithm
  rc4_safe (& g_rc4SafeCtx, InstNum, cbData, pbData);

  return RPC_S_OK;
};

// Select RC4 instance 
void rc4_safe_select (
  pRC4_CONTEXT pRC4Ctx, DWORD * pInstNum, DWORD * pAccumulator)
{
  g_rc4TotalRequests ++;
  * pInstNum = g_rc4TotalRequests & (pRC4Ctx-> InstanceCount - 1);
  * pAccumulator = pRC4Ctx-> Rc4Ins [* pInstNum] -> Accumulator;
};

// Thread-safe wrapper for RC4 call 
void rc4_safe (pRC4_CONTEXT pRC4Ctx, DWORD InstNum, DWORD cbData, BYTE * pbData)
{

  EnterCriticalSection (& pRC4Ctx-> Rc4Ins [InstNum] -> CS);
  rc4 (& pRC4Ctx-> Rc4Ins [InstNum] -> State, cbData, pbData);
  LeaveCriticalSection (& pRC4Ctx-> Rc4Ins [InstNum] -> CS);
};

// Classic implementation of the RC4 algorithm 
void rc4 (PRC4_INSTANCE_STATE pRC4State, DWORD cbData, BYTE * pbData)
{
  BYTE t = 0;

  for ( int p = 0; p <cbData; p ++)
  {
    pRC4State-> i = (pRC4State-> i + 1) & 0x0FF; 
    pRC4State-> j = (pRC4State-> j + pRC4State-> SBOX [pRC4State-> i]) & 0x0FF;
    t = pRC4State-> SBOX [pRC4State-> i];
    pRC4State-> SBOX [pRC4State-> i] = pRC4State-> SBOX [pRC4State-> j];
    pRC4State-> SBOX [pRC4State-> j] = t;
    * (pbData + p) = 
      * (pbData + p) ^ pRC4State-> SBOX [(pRC4State-> SBOX [pRC4State-> i] 
      + pRC4State-> SBOX [pRC4State-> j]) & 0xFF];
  };
  
};

Obviously, there are no irreversible transformations in the algorithm of the UUID generator, and it is based on the stream cipher RC4 [6]. The global structure g_rc4SafeCtx, containing 8 independent instances of the stream cipher states (hereinafter referred to as instances), and the global counter g_rc4TotalRequests, on the basis of which the switching between them occurs, completely describes the state of the entire generator. Each instance has its own S-box and stores the values ​​of two cipher registers. When you call GenerateRandomNumber, the next instance of RC4 is selected (with index (g_rc4TotalRequests + 1) mod 8), which should ensure uniform utilization of S-boxes.

Formally, the generation algorithm can be represented as a diagram shown in Figure 1.

Figure 1. UUID generation scheme in Windows OS.

When you want to create the i-th in a row UUID-value ( U _i ), the generator performs the following actions:

• The global access count is incremented: g_rc4TotalRequests ++ .
• The RC4 instance index is calculated: k _i = g_rc4TotalRequests mod 8 (in order not to overload the circuit, these two operations in Fig. 1 are combined into one k _i  = (k _i-1  +1) mod 8 ).
• The S _k instance of RC4 selected in this way sets the current state of the stream cipher (S-box and the values ​​of the two registers).
• Over the value of I _i , which was initialized buffer * Uuid with the i- th call to UuidCreate , and 16 bytes of the gamut RC4 O _i , the XOR operation is performed: C _i  = O _i  XOR I _i .
• The version of the UUID is specified: U _i [7] = (C _i [7] & 0x0F) | 0x40 .
• Specifies that they belong to RFC4122: U _i [9] = (C _i [9] & 0x3F) | 0x80 .

Initialization of RC4 instances and generator structures

When rpcrt4.dll is loaded, the function rc4_safe_startup is called. It allocates from the heap of the target process the required memory capacity for the g_rc4SafeCtx structure, sets the value of all batteries to 0xFFFFFFFF, and initializes the critical sections of RC4 instances. Thus, each process will have its own state of the Uuid generator.

The instance S-block is initialized when it is first accessed or when the counter byte of the output (Accumulator) of this instance begins to exceed 500,000 bytes. Therefore, before the entire generator is reinitialized, at least 250,000 Uuid values ​​(8 instances * 500,000 bytes = 16 bytes * 250,000 Uuid values) must be created with it. It is also important that the state of the generator can be considered fully defined only after the process calls UuidCreate 8 or more times.

RPC_STATUS GenerateRandomNumber (BYTE * pbData, DWORD cbData) 
{

  // Total number of bytes of output of the current RC4 instance 
  // since its initialization

  DWORD Accumulator = 0;  

  // Number of the current RC4 instance
  DWORD InstNum;

  // Buffer for RC4 key, if initialization is required
  PVOID RandomKey;

  rc4_safe_select (& g_rc4SafeCtx, & InstNum, & Accumulator);

  if (Accumulator> = 500000)
  {
    //Initialization
    
    // Generate a pseudo-random key for RC4 
    if (! SystemFunction036 (RandomKey, 256))
       return RPC_S_OUT_OF_MEMORY;

    // Initialize the RC4 instance
    rc4_safe_key (& g_rc4SafeCtx, InstNum, 256, (BYTE *) RandomKey);
  };

  // The full code of this function was given in the previous section of the article, so 
  // here we will limit ourselves only to the section relating to initialization
... 
};

The mysterious function SystemFunction036 from advapi32.dll has another, more intelligible name - RtlGenRandom (“Georgy Ivanovich, he's Goga, he's Gosh, he's Yuri, he's Jora, does he live here?”). It is under this sign that it can be found in the MSDN annals [7]:

BOOLEAN RtlGenRandom (
  __out PVOID RandomBuffer,
  __in ULONG RandomBufferLength
);

The function is able to directly access Windows PRNG to get a pseudo-random byte sequence and, unlike CryptGenRandom, does not require the indication of a crypto-provider. The fact that SystemFunction036 is the shortest path to the generator is easy to follow with a debugger (the listing shows a call stack from CryptGenRandom):

> advapi32.dll!_SystemFunction036@8 ()   
   rsaenh.dll!_FIPS186Gen@28 () + 0x5f bytes  
   rsaenh.dll!__CPGenRandom@12 () + 0x33 bytes  
   advapi32.dll!_CryptGenRandom@12 () + 0x3d bytes  

Guided by popular wisdom "the farther into the forest, the fatter the guerrillas," we will not (at least for now) delve into the wilds of the PRNG Windows device. First, describing the rather complicated CryptGenRandom algorithm here does not make much sense, since the proposed attack model has nothing to do with the OS pseudo-random number generator. Secondly, researchers from The Hebrew University of Jerusalem in their work " Cryptanalysis of the Number Generator of the Windows Operating System"[8] coped with this task much better by examining the structure of the PRNG, as they say, on the shelves. The only thing worth paying attention to is the striking similarity of both generators - both UuidCreate and CryptGenRandom support 8 instances of RC4, which they use in a round-robin manner.

Another function, rc4_key, directly involved in the initialization of an S-block of an instance, is called in the critical section rc4_safe_key and is a classic implementation of the RC4 Key Scheduling Algorithm (KSA) [6]. The code responsible for the key tiling (if the key length is less than 256 bytes, the key, according to the KSA algorithm, is repeated until the entire 256-byte key array is filled) was omitted in order to save space (the length of the key transmitted in rc4_key from GenerateRandomNumber is always 256, so the rejected code does not play any role).

// Thread-safe wrapper for calling KSA 
void rc4_safe_key (
   pRC4_CONTEXT pRC4Ctx, DWORD InstNum, DWORD cbData, BYTE * pbData)
{

  EnterCriticalSection (& pRC4Ctx-> Rc4Ins [InstNum] -> CS);

  // RC4 Key Scheduling Algorithm (KSA)
  rc4_key (& pRC4Ctx-> Rc4Ins [InstNum] -> State, cbData, pbData);

  LeaveCriticalSection (& pRC4Ctx-> Rc4Ins [InstNum] -> CS);
};

// RC4 Key Scheduling Algorithm (KSA) 
void rc4_key (PRC4_INSTANCE_STATE pRC4State, DWORD cbData, BYTE * pbData)
{
  BYTE t = 0;

  for (pRC4State-> i = 0; pRC4State-> i <256; pRC4State-> i ++)
    pRC4State-> SBOX [pRC4State-> i] = pRC4State-> i;

  pRC4State-> j = 0;
  for (pRC4State-> i = 0; pRC4State-> i <256; pRC4State-> i ++)
  {
    pRC4State-> j = (
      pRC4State-> j 
      + pRC4State-> SBOX [pRC4State-> i] 
      + (* (pbData + pRC4State-> i))
    ) & 0x0FF;
  };

  t = pRC4State-> SBOX [pRC4State-> i];
  pRC4State-> SBOX [pRC4State-> i] = pRC4State-> SBOX [pRC4State-> j];  
  pRC4State-> SBOX [pRC4State-> j] = t;

};

Thus, we arrive at the following scheme for initializing RC4 instances:

1. Before an instance is used to generate Uuid values, its counter byte output (Accumulator) is checked. If it is greater than or equal to 500,000, the instance S-block must be pre-initialized.
2. Using the SystemFunction036 function, which accesses the Windows PRNG, a random 256-byte randomKey is calculated.
3. The key is passed to the KSA algorithm that performs permutations of the S-block of the instance. The nature of the permutations depends only on the RandomKey key.

No gods burn pots

I would like to look into the eyes of a Hindu who used the safe word in the name of the function rc4_ safe _select and didn’t take care of the threads to synchronize when accessing the global variable g_rc4TotalRequests in her body. Either the sclerosis of the young man overcame, or the matter tended to be released - we are unlikely to find out now. But we can admire the effects.

Figure 2 shows the situation when two competing streams access rc4_safe_select and under certain circumstances get the same InstNum and Accumulator values.

1. Two threads in the same process called rc4_safe_select (suppose, for example, the value of a global variable at this stage is 4).
2. Suppose that the time slot allocated by the operating system to Thread 1 expires exactly after the instruction g_rc4TotalRequests ++ (the value has increased by 1: g_rc4TotalRequests = 5).
3. Windows switches the context to Thread 2, which again increments the variable (now its value becomes 6).
4. Control passes to Thread 1 (the variable is still 6).
5. Both in the first and second streams, the function returns the same InstNum and Accumulator values.

Figure 2. The lack of synchronization in the body of rc4_safe_select leads to an unpredictable result.

The consequences are obvious:

1. Both streams will work with the same RC4 instance. And the stream that reached rc4_safe last will expect a “favorite of the race” in the critical section.
2. Use of instances becomes inconsistent. This is indicated, in particular, by the difference in the values ​​of batteries, sometimes reaching 10% (with a sequential cyclic reference to instances a la “round-robin”, this simply cannot be observed).
3. If the Accumulator exceeds 500,000, the corresponding instance of RC4 will be initialized twice — first with the first thread and then with the second — which will undoubtedly have an impact on performance.

The described error is not so critical as to fertilize the bald spot with ashes or dig in the nearest cave in anticipation of the apocalypse. However, getting rid of it will not be superfluous at all, especially since it can be done with a light stroke of the pen:

// Select RC4 instance 
void rc4_safe_select (
   pRC4_CONTEXT pRC4Ctx, DWORD * pInstNum, DWORD * pAccumulator)
{
  DWORD l_RC4TotalRequests;
  // Deadlock on incrementing
  l_RC4TotalRequests = InterlockedIncrement (& g_rc4TotalRequests);
  * pInstNum = l_RC4TotalRequests & (pRC4Ctx-> InstanceCount - 1);
  * pAccumulator = pRC4Ctx-> Rc4Ins [* pInstNum] -> Accumulator;
};

or the same, but for art lovers:

// Select RC4 instance 
void rc4_safe_select (
   pRC4_CONTEXT pRC4Ctx, DWORD * pInstNum, DWORD * pAccumulator)
{
  DWORD l_RC4TotalRequests;

  __asm {
    mov       eax , 1
    lock xadd g_rc4TotalRequests, eax 
    inc       eax 
    mov l_RC4TotalRequests, eax
  };
  * pInstNum = l_RC4TotalRequests & (pRC4Ctx-> InstanceCount - 1);
  * pAccumulator = pRC4Ctx-> Rc4Ins [* pInstNum] -> Accumulator;
};

You can learn more about deadlock functions in MSDN [9].

With a sword bald

The determinism inherent in the software (and in some cases hardware) implementation of any algorithm is the true Achilles heel of cryptographic systems. And sadly enough, it is the implementation errors that discredit the protected environment more often than the vulnerabilities found in mathematical models. The matter is further complicated by the fact that developers sometimes deliberately refuse to use persistent protection mechanisms, explaining this, for example, by the inability to ensure maximum speed combined with an acceptable level of security. Moreover, the “contract with conscience” clause is not limited to the clause on impaired productivity. With no less success, other “obstructive arguments” are also going on. Let us recall at least our remote attack on MS SQL Server [10] with Jan Lieberman, which we would not be able to do, Do not be secure in the TDS protocol sacrificed to the “feature” of backward compatibility with less protected clients. So traces of compromises can be found in almost any applied solution and the results of the UuidCreate study confirm this once again.

A cryptographically reliable pseudo-random number generator should not only produce a sequence that seems seemingly random at first glance, but also have two important properties - Backward and Forward Security.

Backward security - does not allow an attacker to predict the states in which he will be in the future according to the current state of the generator. To reduce the detrimental effect of determinism and to at least somehow meet this requirement, the algorithm usually provides for regular state updates ( rekey) a true random bit sequence. And the more often it is executed, the more resistant is the generator. Entropy sources can be indications of performance counters, measurements of thermal sensors, processor registers values ​​at a certain point in time, and other values ​​remaining secret to an intruder with seven seals (refer to the book by Michael Howard and David Leblank Protected Code [11], where the authors without regretting the paper, more than a hundred sources for CryptGenRandom were listed separated by commas

Now we already know from what test the Uuid generator was made and with confidence we can say - it does not stand the test for backward security . A full status update occurs after 4 · 10 ⁶ bytes of output (8 instances of RC4 * 500,000 bytes), so an attacker who managed to get the “cast” of all the registers and S-blocks of UuidCreate at a certain point in time can predict up to 250,000 future Uuid -values Moreover, the generator's GPS entropy is represented by SystemFunction036, which, given the predictability of the latter [8], increases the length of the compromised data stream to an extreme 256 · 10 ⁶ bytes!

Indeed, CryptGenRandom, like UuidCreate, consists of 8 instances of RC4. Each of them goes through the re-initialization procedure, when the output byte counter begins to exceed 16 KB. This is almost 30 times less than that of the Uuid-generator, but not enough to be considered reliable. RC4 instances in CryptGenRandom are used evenly, therefore, a full update of the PRNG state is performed only after 128 KB of output (8 instances of RC4 * 16 KB).

The rc4_safe_key function consumes 256 bytes of the Windows PRNG exit per one reinitialization of an instance in the Uuid generator, while 2 KB is spent on a full update (8 instances * 256 bytes of the key). By simple arithmetic operations, it is easy to calculate how many Uuid-values ​​an attacker can predict if he can get the current state of CryptGenRandom:

4 · 10 ⁶ * (128 Kb / 2 Kb) = 256 · 10 ⁶ bytes;

256 · 10 ⁶ bytes / 16 bytes in one Uuid-value = 16 · 10 ⁶ Uuid-values

Figure 3. The hierarchy of sources of entropy.

You will ask why it was necessary to use a surrogate derived from PRNG Windows instead of sources of entropy of the OS. I'll start from afar. First of all, no one in their right minds placed great hopes on the resilience of UuidCreate (and those who have laid are simply obliged to read this article to the end). The demiurgists themselves clearly stated their position in RFC4122 [1]: “Do not assume that the UUIDs are hard to guess; they should not be used as security requirements, for example. A predictable random number source will exacerbate the situation ». So developers never had a goal to create a safe Uuid generator. Unfortunately, the planet Earth is still trampling on goblins (not only trampling, but also express payment cards are stamped!), Which apply to such warnings without proper trepidation.

Secondly, for unnecessary access to the system registry key, where the 80-byte Seed is stored, or calling the function of the KSecDD driver, you will have to pay with expensive CPU time ticks (.NET chikam cannot understand;) This will be especially noticeable in the latter case, since it requires switching to kernel mode (here's a compromise between performance and security). Third, it is much easier to create a pseudo-random key for RC4 using SystemFunction036 rather than complicate your life with the overly complicated generator design.

We now turn to the second property of reliable PRNG - Forward Security . Its meaning is that the attacker who owns the current state of the generator should not extract any information about the previous output from it. In other words, PRNG should be designed as a unidirectional function, using hashing algorithms for this purpose.

But here, UuidCreate fails. The only transformations that we see in the code are limited to permutations inside S-boxes. An attacker can easily perform these operations in the reverse order and obtain the preceding gamma of the generator:

void rc4_revert (PRC4_INSTANCE_STATE pRC4State, DWORD cbData, BYTE * pbData)
{
  BYTE t = 0;

  for ( int p = cbData - 1; p> = 0; p--)
  {
    * (pbData + p) = 
      * (pbData + p) ^ pRC4State-> SBOX [(pRC4State-> SBOX [pRC4State-> i]
      + pRC4State-> SBOX [pRC4State-> j]) & 0xFF];
    t = pRC4State-> SBOX [pRC4State-> i];
    pRC4State-> SBOX [pRC4State-> i] = pRC4State-> SBOX [pRC4State-> j];
    pRC4State-> SBOX [pRC4State-> j] = t;
    pRC4State-> j = (pRC4State-> j - pRC4State-> SBOX [pRC4State-> i]) & 0x0FF;
    pRC4State-> i = (pRC4State-> i - 1) & 0x0FF; 
  };
  
};

So, suppose the attacker took a memory “cast” from the g_rc4SafeCtx structure and remembered the g_rc4TotalRequests call count at a time t such that T ₁ ? t? T ₂ , where T ₁ is the time of the last complete generator update, and T ₂ is the time of the upcoming update. Then it can reproduce the output of the generator in the interval [T ₁ ; t) and predict the values ​​returned by the UuidCreate function until the occurrence of T ₂ .

There is, however, one nuance that must be taken into account. The value of the buffer I _i transmitted to UuidCreate in the i-th call is not always known to the attacker. And according to the scheme shown in Figure 1, an XOR operation is performed between this value and the gamut of RC4. Therefore, at first glance, it seems that an attacker who does not know I _i will hardly be able to use the proposed attack model. However, in practice, the Uuid variable is either initialized with zeros, or it contains garbage that is on the stack by the time the memory is allocated. In the latter case, the probability of occurrence of correlations between different values ​​of I _i in the interval from T ₁ to T ₂ It remains quite high, than the attacker will not fail to take advantage of (I will show it a little lower using the example of MS SQL Server).

Now that you are familiar with the anatomy of UuidCreate and have mastered the theoretical part of the article, I would like to say a few words about the console utility Uuid Big Brother , which I wrote to automate the attack procedure. The utility is able to take a dump of the state of the Uuid-generator in any of the OS processes and to guess both the previous and the subsequent Uuid-values ​​(for a detailed description of the UBB parameters, see Appendix B).

Attack with the famous Ii

As a warm-up, I propose to hone our oracle skills on a simple guidgen.exe application, from time immemorial included in the delivery of Visual Studio [12]. This utility is noteworthy because before calling UuidCreate, the buffer for the Uuid-value is initialized with zeros (that is, I _i == NULL). You can see this for yourself since the guidgen source code is available for download to everyone [13]:

// Guidgdlg.h 
void CGuidGenDlg :: OnNewguid ()
{
  // create random GUID using uUidCreate so that we 
  // can check for more error codes
  m_guid = GUID_NULL;
  HRESULT hr = :: UuidCreate (& m_guid);
  
  // ...
}

This is definitely a chance to exercise in foresight.

1. Run guidgen.exe and find it in the Task Manager. Remember the process ID (for example, PID = 3912).
2. Remove the generator state dump with the help of Uuid Big Brother and save it to the guidgen.dmp file:

ubb -d3912 "c: \ ubb \ guidgen.dmp"

The result of the command will be approximately as follows:

Warning: not all the RC4 instances were initialized. Please initiate 8 UUIDs generation.

State was successfully dumped to file c: \ ubb \ guidgen.dmp.

UBB hints to us that the process did not have time to initialize one or more RC4 instances, so part of the predicted Uuid values ​​will not be true.

1. Press the New Guid button 7 times in the GuidGen window (this will force the application to completely initialize the generator), then re-take the dump. The warning should disappear:

ubb -d3912 "c: \ ubb \ guidgen.dmp"
--------------------------------
State was successfully dumped to file c: \ ubb \ guidgen.dmp.

1. Now run ubb with the –g parameter (nothing prevents you from doing this on another machine, after copying the dump file there). The –g option causes the utility to predict all subsequent Uuid values.

ubb -g "c: \ ubb \ guidgen.dmp"
--------------------------------
EAC00EFD-68DB-449F-9350-8954C2300DA2
D2DD36ED-6620-4CC9-80BE-9569EFD00FA5
D60CF120-A6DA-4B4B-84F1-2C1BD6EDC071
1F00F7F3-8F0F-4473-80F2-D3B175CC93DB
 ADA0FB01-85C0-4D67-86D1-925C68373F22
82D781D6-489A-46D6-9F9F-47265F76DB38
F10E5C71-5561-4999-9AF7-16CB1D80B0A0
050E5489-AAB3-4837-A240-92B4B165D588

1. Click the New Guid button again in the GuidGen window. The Result section displays the Uuid-value (in the screenshot {1F00F7F3-8F0F-4473-80F2-D3B175CC93DB}), which you managed to guess before the application generated it (in the 4th step in bold).

Pressing any key in UBB results in new values. By default, the utility issues them in portions of 8 elements each, but you can change this number using the –o key (for more details, see Appendix B).

Attack with unknown Ii

The time has come to recollect Vasily Razdolbayev and find out how he managed to circle the children from the White Collars department around his finger. But first, make sure that the T-SQL function NEWID () actually uses the Windows UUID generator, and that the attack technique described here is applicable to scenarios with express payment cards. The listing shows the recovered code for MS SQL Server 2008 CTP5 (build 1075):

; sqlservr.exe
; void __fastcall GuidNewid (class CEsExec *, class CXVariant *)
? GuidNewid @@ YIXPAVCEsExec @@ PAVCXVariant @@@ Z proc near
                mov      edi , edi 
                push     esi 
                mov      esi , edx 
                lea      eax , [ esi +4]
                push     eax              ; pguid 
                call __imp__CoCreateGuid @ 4 ; CoCreateGuid (x) 
                test     eax , eax 
                jnz      short loc_1A07597
                mov [ esi ], al

loc_1A07597:          
                pop esi
                retn
? GuidNewid @@ YIXPAVCEsExec @@ PAVCXVariant @@@ Z endp

; ole32.dll
; long __stdcall wCoCreateGuid (struct _GUID *)
 ? wCoCreateGuid @@ YGJPAU_GUID @@@ Z:
                 mov      edi , edi 
                 push     ebp 
                 mov      ebp , esp 
                 push     esi 
                 push [ ebp + lp]         ; Uuid 
                 call     ds : __ imp__UuidCreate @ 4 ; UuidCreate (x) 
                 mov      esi , eax 
                 cmp      esi , 720h
                 jz       short loc_776A5659
                 test     esi , esi
                 jnz loc_776EDF0E

 loc_776A5659:    
                 xor      eax , eax

 loc_776A565B:    
                 pop      esi 
                 pop      ebp
                 retn 4
 _CoCreateGuid @ 4 endp

The next step is to figure out how the Ii buffer is initialized before running UuidCreate. To do this, we need SQL Internals Profiler - a tool developed by Jan Lieberman and indispensable in cases where you need to collect statistics on calls to the internal functions of MS SQL Server. Now, in particular, we will be interested in the values ​​passed by the pguid pointer to the CoCreateGuid.

- Enable interception of the CoCreateGuid function by splicing
 exec xp_SQLInternalsProfiler_AddSource_Splicing 'ole32.dll',
  'CoCreateGuid', 'hpg1; -', 1

Translated from Liberman, the phrase 'hpg1; -' sounds like this: “The first parameter (1) of the function is a reference (p) to an archival value 16 bytes long (h) that needs to be intercepted before calling CoCreateGuid (;-). Group results by unique values ​​(g) ". Those who wish to master this language can recommend an excellent Russian-Liberian phrasebook [14,15].

Let's see how NEWID behaves if you periodically contact it:

- We reset the accumulated exec xp_SQLInternalsProfiler_ClearAll statistics


print NEWID ()
waitfor delay '00: 00: 05 '
print NEWID ()
waitfor delay '00: 00: 05 '
print NEWID ()
waitfor delay '00: 00: 05 '
print NEWID ()
waitfor delay '00: 00: 05 '
print NEWID ()

- Display the result
 EXECUTE xp_SQLInternalsProfiler_Results 147

I got the following picture (SQL Server 2008 CTP5):

We see that I _i (the binary_grpup_id field) was changed every time the NEWID function was called, although the difference in values ​​is not so great - only 25% (4 bytes from 16 are bold). The server does not bother to initialize * pguid, so the garbage is constantly being transmitted to CoCreateGuid. Thus, for example, the double word 0xF9E30A01 is the return address from CreateExecValSeg:

010AE3F4 call CEsCompValSeg :: CreateExecValSeg
010AE3F9 pop edi
...  

Or here's another funny arithmetic (subtract the second double word from the fourth):

0x04AE61C0 - 0x04AE6130 = 0x90
0x04AE63C8 - 0x04AE6338 = 0x90
0x04AE65D0 - 0x04AE6540 = 0x90
... 

The correlation found reduces the entropy level I _{i by} half (from 2 ³² to 2 ¹⁶ ), since the number of independent unknowns has decreased. You shouldn’t disregard the “vertical” pattern (we subtract the second double word on i + 1 iteration from it on i-iteration):

0x04AE6338 - 0x04AE6130 = 0x208
0x04AE6540 - 0x04AE6338 = 0x208
0x04AE6748 - 0x04AE6540 = 0x208
... 

So, if we recognize I _i , then we can easily calculate I _{i + 1} . Moreover, any I _i unpredictable are only 2 bytes.

Restart MS SQL Server and repeat the experiment:

The new results indicate that 8 bytes remain unchanged, and the correlations persist after the restart.

Of course, fully relying on these observations would be too rash. Let's try to simulate a situation where Uuid identifiers are not only created, but also inserted into the table field:

create  table #pin_codes (
  id int identity
  , pin_code varchar (36)
)
go

- We
 reset the accumulated exec xp_SQLInternalsProfiler_ClearAll statistics

declare
  @i int = 0

while (@i! = 10000) begin

  insert #pin_codes values (newid ())
   set @i + = 1
 end

- Display the result 
EXECUTE xp_SQLInternalsProfiler_Results 147

It turns out that any use of NEWID in cyclic operations (not necessarily when inserted into a table) demonstrates an enviable constancy of the values ​​of Ii. Over 10,000 iterations, it changed only once!

It is very unlikely that PIN codes for express payment cards were generated “individually”, as in the first experiment. Therefore, the asocial element Razdolbaev will appreciate this gift of fate. However, the total entropy of the set {I ₁ , I ₂ , ... I _n } in both cases will be the same - 2 ³² . It would be possible to mention other ways to call NEWID, but almost all of them (there are exceptions, I will not lie) come down either to the statistics collected in the experiment with wait for, or to the results of the exercise with the cycle. Similar tests for MS SQL Server 2000/2005 reveal approximately the same correlations.

When single calls to NEWID we observe "vertical" pattern that allows us I of _i calculate {I of _{i + 1} , I of _{i + 2} , ... I of _{i + n} }. And if the function was used in a cycle, then I _i = I _{i + 1} = I _{i + 1} = ... = I _{i + n} . Therefore, to restore the entire sequence, an attacker needs to calculate at least one value I _i . And here he comes to the aid of the property of reversibility of the operation XOR. In the generator algorithm, there is a stage where an exclusive OR is performed between the gamma RC4 O _i and the value of I _i :

C _i = O _i XOR I _i => I _i = O _i XOR C _i

U _i [1..6] = C _i [1..6]

U _i [7] = (C _i [7] & 0x0F) | 0x40

U _i [8] = C _i [8]

U _i [9] = (C _i [9] & 0x3F) | 0x80

U _i [10..16] = C _i [10..16]

We introduce I ' _i = O _i XOR U _i , where I' _i differs from I _{i by} several bits in 7 and 9 bytes.

We show that replacing I _i with I ' _i in direct calculations gives the same value U _i :

C ' _i = O _i XOR I' _i

C ' _i [1..6] = C _i [1..6] = U _i [1..6]; C ' _i [8] = C _i [8] = U _i [8]; C ' _i [10..16] = C _i [10..16] = U _i [10..16];

C ' _i [7]? C _i [7]; C ' _i [9]? C _i [9], but

U ' _i [7] = (C' _i [7] & 0x0F) | 0x40 = (C _i [7] & 0x0F) | 0x40 = U _i [7]

U ' _i [9] = (C' _i [9] & 0x3F) | 0x80 = (C _i [9] & 0x3F) | 0x80 = U _i [9]

Hence, U ' _i = U _i and the replacement of I' _i by I _i is valid.

Suppose Razdolbaev bought one payment card in the nearest stall and found the PIN code U _k under a protective layer . Our calculations will help him calculate I _k only if he knows at what iteration of the Uuid generator the given PIN code was received. In other words, Razdolbaev should know k. This problem can be solved by resorting to the enumeration of the values ​​of O _i generated by the generator in the interval between two complete state updates [T ₁ ; T ₂ ]. And now Vasily will have to fork out not for one, but for as many as three payment cards (PIN codes P _x , P _y and P _z ).

BOOL InOrder = FALSE;

For i from 1 to 250 000 {
  For j from 1 to 250 000 {
    If (Oi XOR Px) == (Oj XOR Py) {
      // Perhaps x = i, y = j
      For k from 1 to 250 000 {
        If (Oi XOR Px) == (Ok XOR Pz) {
          // x = i, y = j, z = k 
          // Ii = Ij = Ik = (Oi XOR Px)
          InOrder = TRUE;
        }  
      }
      If (! InOrder) {
        // x = j, y = i, z = k 
        // Ii = Ij = Ik = (Oi XOR Py)
      }
    }
  }    
}

The method is based on the assumption that with each subsequent call to UuidCreate, the value of _{i i} does not change. However, the same idea is easy to adapt to the case when I _i remains constant only a few bytes. For example, for single calls to NEWID enough to treat the '=' sign of equality any 8-byte values of 16 are limited only part I of _i , we are in the long run no risk, because the probability of the existence About _i and About _j such that (About _i XOR P _x ) = [8] (O _j XOR P _x ) with i? j is negligible.

Values ​​that satisfy the condition (O _i XOR P _x ) = (O _j XOR P _y ) will also satisfy (O _i XOR P _y ) = (O _j XOR P _x ), and (O _i XOR P _x )? (O _i XOR P _y ). To determine which of the two options is correct, it is necessary to perform another morning run over the set {O _i }:

• If (O _i XOR P _x ) = (O _k XOR P _z ), then the correct answer is I _i = (O _i XOR P _x )
• If there is not a single O _k where this relationship holds, then I _i = (O _i XOR P _y ).

We will set up an investigative experiment, where we will play the role of Vasya Razdolbaev.

1. On a machine with a running instance of MS SQL Server 2000/2005/2008, find the process sqlservr.exe in the Task Manager (Task Manager) and note its identifier (let it be PID = 1508).
2. Remove the generator state dump with the help of Uuid Big Brother and save it in the sqlservr.dmp file:

ubb –d1508 "c: \ ubb \ sqlservr.dmp"

Razdolbaev should have done these two steps on April 14, on the eve of the PIN code generation procedure.

1. After some time, model the creation of “random” PIN codes to payment cards (according to the scenario, White Collars are filling the table with Uuid IDs, and Vasily is at a corporate party at this moment):

create table #pin_codes (
  id int identity, 
  pin_code varchar (36)
)
go

set nocount on
declare
  @i int 

set @i = 0
while (@i! = 10000) begin

  insert #pin_codes values ​​(newid ())
  set @i = @i + 1
end

1. Take any three values ​​of the #pin_codes table and save to known_uuid.txt. Do not worry about Razdolbaeva. On April 16, he bought three cards of a new series and added PIN codes found under a protective layer to known_uuid.txt.

Each value should be located on a new line.

1. Run the UBB utility on another computer by copying sqlservr.dmp and known_uuid.txt there.

ubb -g -ik "known_uuid.txt" -ab8 -of "pins.txt" "sqlservr.dmp"

----------------------------------
Analysis started. Press <Ctrl> + <Break> to abort.
Analyzing ... |
Known UUID # 1 index: 1594
Known UUID # 1: 9EF15183-EFB9-4FCC-B9A5-5321E7A15385
Gen output # 1: 9EF15183-EFB9-4FCC-8D50-0742E7A15385
Initial val # 1: 00000000-0000-0000-34F5-546300000000

Known UUID # 2 index: 73
Known UUID # 2: 7D7EE0E8-3BE3-409D-B56B-BF6118F48C33
Gen output # 2: 7D7EE0E8-3BE3-409D-819E-EB0218F48C33
Initial val # 2: 00000000-0000-0000-34F5-546300000000

Known UUID # 3 index: 6101
Known UUID # 3: 7F7DF678-FD5A-418F-BBC2-289031D79174
Gen output # 3: 7F7DF678-FD5A-418F-8F37-7CF331D79174
Initial val # 3: 00000000-0000-0000-34F5-546300000000

Common initial: 00000000-0000-0000-34F5-546300000000
Uuids was successfully saved to file pins.txt.

Assign Parameters

1. -g: calculate the next generator output relative to the state stored in the sqlservr.dmp file.
2. -of "pins.txt": output the predicted Uuid identifiers to pins.txt.
3. -ik "known_uuid.txt": I _i must be calculated from the three known Uuid-values ​​that are contained in the file known_uuid.txt.
4. -ab8: if any 8 bytes of I _x match any 8 bytes of I _y , then I _x = I _y . The larger the parameter value, the longer the search for I _i is performed . But I do not recommend specifying less than 8.

Interpretation of the result

Known UUID #n: string n in the file known_uuid.txt.

Known UUID #n index: the sequence number i of the UuidCreate call from the moment the "cast" of the generator state was taken.

Gen output #n: Oi corresponding to the given Pi.

Initial val #n: Ii corresponding to the given Pi.

Check how accurate the predictions are. Select the first value you like from the table and look for it in the pins.txt file.

Appendix A. Put a wheelbarrow on the download

Uuid Big Brother utility, version 1.0.0, © Nikolay Denishchenko

The console utility Uuid Big Brother should be used exclusively for educational, health and recreational purposes. The author is not responsible for any damage, directly or indirectly caused by using it.

Download the utility along with the installer

Download utility without installer (console + VC runtime library)

Parameter descriptions and application tips can be found in Appendix B.

SQL Internals Profiler, version 1.0.3, © Yan Liberman

Download installer

Guide and description

Examples of using

Appendix B. Uuid Big Brother Utility Options

In order for the utility to be able to gain unhindered access to the memory of the external process, it must be run on behalf of an account with the authority of Debug Programs (for example, on behalf of the local system administrator).

Common syntax

ubb [<switches> ...] <dump_file>

Reference output

Combining information keys with other parameters is not allowed.

Generator state dump

If not all RC4 instances are initialized by the process (less than 8 calls to UuidCreate were made during its operation), you will receive the message:

Warning: not all the RC4 instances were initialized. Please initiate 8 UUIDs generation.

This warning means that the state of only those instances that are already initialized at the time of recording and therefore their output is predefined is saved to the dump file. The sequence of UUID values ​​predicted by the utility based on an incomplete dump file will contain “gaps”. Often, this situation occurs at the very beginning of the target process or in situations where the process very rarely calls UuidCreate.

If the operation is successful, the following message is displayed:

State was successfully dumped to file <dump_file>.

Generator state analysis and value prediction

Appendix B. Investigated versions of the rpcrt4.dll library

References and references

RFC4122

UUID (Wikipedia)

GUID (Wikipedia)

UUID Structure (MSDN)

UuidCreate Function (MSDN)

RC4 (Wikipedia)

RtlGenRandom (MSDN)

"Cryptanalysis for Windows Operating System", Leo Dorrendorf, Zvi Gutterman, Benny Pinkas

Interlocked Variable Access (MSDN)

Materials to the report "Analysis of the possibility of a remote attack on MS SQL Server 2000-2008", Nikolay Denishchenko, Jan Lieberman

"Protected Code", Michael Howard, David LeBlanc

Visual Studio guidgen.exe (MSDN)

GUIDGEN Sample: Generates Globally Unique Identifiers (MSDN)

SQL Internals Profiler, Jan Lieberman

SQL Internals Profiler (usage examples), Jan Lieberman

Copyright © 1994-2016 K-Press Ltd.

Original text

Contribute a better translation

---